package util.data_structures;
import util.methods.StringHelpers;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.AbstractMap;
import java.util.HashMap;

/*
 * Created on Jun 29, 2005
 *
 */

/**
 * @author brian
 *
 */
public class PrefixTree 
{
	public int size ()
	{
		// Add in the current nodes values
		int nSize = 0;
		if ( values != null )
			nSize += values.size();
		
		// Add in all children
		for ( int i = 0; i < getChildCount (); ++i )
			nSize += children[i].size();
		return nSize;
	}
	
	public void put ( String strKey, Object value )
	{
		// Sanity, no wild card in key
		if ( strKey.indexOf('*') >= 0 )
			throw new RuntimeException ( "Valid keys may not contain '*'." );
		strKey = strKey.toUpperCase();
		
		// Basis case: end of the input string, add value
		// to the current node
		if ( StringHelpers.isEmpty(strKey) )
		{
			if ( values == null )
				values = new ArrayList<Object> ( 1 );
			values.add( value );
			return;
		}
		
		// Look for a match to the first character of the string
		char ch = strKey.charAt(0);
		for ( int i = 0; i < getChildCount (); ++i )
		{
			// Found matching link, recurse with key minus
			// the first character
			if ( linkLetters[i] == ch )
			{
				// Found matching link, recurse with key minus
				// the first character
				children[i].put ( strKey.substring(1), value );
				return;
			}						
		}
		
		// Link for letter doesn't exist yet, copy old arrays
		int nNewLength = getChildCount () + 1;
		char newLinkLetters [] = new char [ nNewLength ];
		PrefixTree newChildren [] = new PrefixTree [ nNewLength ];
		
		for ( int i = 0; i < getChildCount (); ++i )
		{
			newLinkLetters [i] = linkLetters[i];
			newChildren [i] = children[i];
		}
		
		// Add new link and recurse
		linkLetters = newLinkLetters;
		children = newChildren;
		linkLetters [ nNewLength - 1 ] = ch;
		children [ nNewLength - 1 ] = new PrefixTree ();
		children [ nNewLength - 1 ].put ( strKey.substring(1), value );
	}
	
	public ArrayList findExact ( String strKey )
	{
        HashMap matches = new HashMap ();
		find_imp ( "", strKey.toUpperCase(), matches, EXACT_MATCH_ONLY );
        return createOutput ( matches );
	}

	public Object findExactObj ( String strKey )
	{
        HashMap matches = new HashMap ();
		find_imp ( "", strKey.toUpperCase(), matches, EXACT_MATCH_ONLY );
		ArrayList matchList = createOutput ( matches );
		if ( matchList.size() == 1 )
			return matchList.get( 0 );
		else if ( matchList.isEmpty() )
			return null;
		else
			throw new RuntimeException ( "There are multiple objects mapped to the key." );
	}
	
	public ArrayList findLeadingWild ( String strKey )
	{
        HashMap matches = new HashMap ();
        find_imp ( "", strKey.toUpperCase(), matches, IMPLICIT_WILD_BOTH_ENDS );
        return createOutput ( matches );
	}
	
	private int getChildCount ( )
	{
		if ( linkLetters == null )
			return 0;
		else
			return linkLetters.length;
	}
	
    private ArrayList createOutput ( AbstractMap matches )
    {
    	ArrayList out = new ArrayList ();
        Iterator iter = matches.values().iterator();
        while ( iter.hasNext() )
        {
            out.addAll( (ArrayList)iter.next() );
        }
        return out;
    }
	
	private void find_imp ( String strNodeKey, String strSearchKey, AbstractMap matches, int nExact ) 
	{ 
		// Trim all leading wild cards
		if ( nExact != EXACT_MATCH_ONLY )
		{
			if ( !StringHelpers.isEmpty(strSearchKey) )
			{
				if ( strSearchKey.charAt(0) == '*' )
					nExact = IMPLICIT_WILD_BOTH_ENDS; // Re-open wild at the beginning of the sub-string
					
				int i;
				for ( i = 0; i < strSearchKey.length(); ++i )
					if ( strSearchKey.charAt(i) != '*' )
						break;
					
				strSearchKey = strSearchKey.substring( i );
			}
		}
		
		// Basis case: end of the input string, return
		// all values in the current sub-tree
		if ( StringHelpers.isEmpty(strSearchKey) )
        {
            getAllValuesInTree ( strNodeKey, matches, nExact );
            return;
        }

		// Look for a match to the first character of the string
		char ch = strSearchKey.charAt(0);
		for ( int i = 0; i < getChildCount (); ++i )
		{
			if ( linkLetters [i] == ch )	
			{
				// Found matching link, call non-wild card
				// find with key minus the first character
				int nNewMatch = IMPLICIT_WILD_END;
				if ( nExact == EXACT_MATCH_ONLY )
					nNewMatch = EXACT_MATCH_ONLY;
				children[i].find_imp ( strNodeKey + linkLetters[i], strSearchKey.substring(1), matches, nNewMatch );
			}

			// Recursive call on the non-matching link with
			// key (all leading *'s should be trimmed)
			if ( nExact == IMPLICIT_WILD_BOTH_ENDS )
				children[i].find_imp ( strNodeKey + linkLetters[i], strSearchKey, matches, nExact );
		}
	}
		
	private void getAllValuesInTree ( String strNodeKey, AbstractMap<String,ArrayList<Object>> matches, int nExact )
	{
		// Get all values for the current node that aren't already under the key
        if ( values != null && !values.isEmpty() )
        {
        	ArrayList<Object> results = (ArrayList<Object>)matches.get( strNodeKey );
            if ( results == null )
            {
                results = new ArrayList<Object> (); 
                matches.put ( strNodeKey, results );
            }
            for ( int i = 0; i < values.size(); ++i )
            {
                Object curValue = values.get(i);
                if ( results.indexOf( curValue ) == -1 )
                    results.add( curValue );
            }
        }
        
        if ( nExact != EXACT_MATCH_ONLY )
        {
        	// Recurse on all children and accumulate the results for end of string wild card
    		for ( int i = 0; i < getChildCount (); ++i )
				children[i].getAllValuesInTree ( strNodeKey + linkLetters[i], matches, nExact );
        }
	}
	
	private ArrayList<Object> values = null;
	private char [] linkLetters = null;
	private PrefixTree [] children = null;
	//private int nEntries = 0;
	
	static private final int EXACT_MATCH_ONLY = 0;
	static private final int IMPLICIT_WILD_BOTH_ENDS = 1;
	static private final int IMPLICIT_WILD_END = 2;
}
